#include <iostream>
using namespace std;
/*
void swap(int& a, int& b)
{
	if(&a !=  &b)
		a^=b^=a^=b;
}
*/
void shiftdown(int heap[], int n, int index)
{	
	int next;
	while(1)
	{
		next = index * 2;
		if(next > n)
			break;
		if(next == n)
		{
			if(heap[index] > heap[next])
				swap(heap[index], heap[next]);
			break;
		}
		if(heap[next+1] < heap[next])
			next++;
		if(heap[index] > heap[next])
			swap(heap[index], heap[next]);
		index = next;
	}
}

void shiftup(int heap[], int n, int index)
{
	int next;
	while(1)
	{
		next = index / 2;
		if(next == 0)
			break;
		if(heap[next] <= heap[index])
			break;
		swap(heap[next], heap[index]);
		index = next;
	}
}

void makeheap(int nonheap[], int n)
{
	for(int i=n/2; i>0; i--)
		shiftdown(nonheap, n, i);
}

void makeheap2(int nonheap[], int n)
{
	for(int i=2; i<=n; i++)
		shiftup(nonheap, n, i);
}

void heapsort(int array[], int n)
{
	makeheap(array, n);
	for(int i=n; i>=2; i--)
	{
		swap(array[i], array[1]);
		shiftdown(array, i-1, 1);
	}
}


void heapsort2(int array[], int n)
{
	makeheap2(array, n);
	for(int i=n; i>=2; i--)
	{
		swap(array[i], array[1]);
		shiftdown(array, i-1, 1);
	}
}

int main()
{
	int array[10+1] = {-1, 4,2,5,6,3,1,7,9,8,0};
	heapsort(array, 10);
	for(int i=1;i<10+1;i++)
		cout << array[i] << " ";
	cout << endl;
	
	int array2[10+1] = {-1, 4,2,5,6,3,1,7,9,8,0};
	heapsort2(array2, 10);
	for(int i=1;i<10+1;i++)
		cout << array2[i] << " ";
	cout << endl;

	return 0;
}
